%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A nonempty string $S$ of characters.
\Ensure A list $L$ of positive integers indicating how the brackets
  match. If the brackets are not balanced, return the empty string
  $\varepsilon$.
%%
%% algorithm body
\State $L \gets [\,]$
\State $T \gets$ empty stack
\State $c \gets 1$
\State $n \gets |S|$
\For{$i \gets 0, 1, \dots, n$}
  \If{\rm $S[i+1]$ is a left bracket}
    \State $\append(L, c)$
    \State push $(S[i+1],\, c)$ onto $T$
    \State $c \gets c + 1$
  \EndIf
  \If{\rm $S[i+1]$ is a right bracket}
    \If{\rm $T$ is empty}
      \State \Return $\varepsilon$
    \EndIf
    \State $(\MyLeft,\, d) \gets \pop(T)$
    \If{\rm $\MyLeft$ matches $S[i+1]$}
      \State $\append(L, d)$
    \Else
      \State \Return $\varepsilon$
    \EndIf
  \EndIf
\EndFor
\If{\rm $T$ is empty}
  \State \Return $L$
\EndIf
\State \Return $\varepsilon$
\end{algorithmic}
